package HOT;

/**
 * Author  zxy
 * Date  2023/7/12 10:24
 */

/*
* 给你一个满足下述两条属性的 m x n 整数矩阵：
* 每行中的整数从左到右按非递减顺序排列。
* 每行的第一个整数大于前一行的最后一个整数。
* 给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。
* */

public class SearchMatrix_74 {
    public boolean searchMatrix(int[][] matrix, int target) {

        int rows = matrix.length;
        int cols = matrix[0].length;

        // int row = binarySearchRow (matrix, target);

        // return row >= 0 ? binarySearchCol (matrix[row], target) : -1;


        // 一次二分查找
        int left = 0;
        int right = rows * cols - 1;

        // if (target < matrix[0][0] || target > matrix[rows - 1][cols - 1]) {
        //     return false;
        // }

        while (left <= right) {
            int mid = (right - left) / 2 + left;

            int row = mid / cols;
            int col = mid % cols;

            if (matrix[row][col] == target) {
                return true;
            }
            else if (matrix[row][col] < target) {
                left = mid + 1;
            }
            else {
                right = mid - 1;
            }
        }

        return false;
    }

    public int binarySearchRow (int[][] matrix, int target) {

        if (target < matrix[0][0]) {
            return -1;
        }

        int left = 0;
        int right = matrix.length - 1;

        while (left < right) {
            int mid = (right - left + 1) / 2 + left;

            if (matrix[mid][0] <= target) {
                left = mid;
            }
            else {
                right = mid - 1;
            }
        }

        return left;
    }

    public boolean binarySearchCol (int[] arrs, int target) {
        int left = 0;
        int right = arrs.length - 1;

        while (left <= right) {
            int mid = (right - left) / 2 + left;

            if (arrs[mid] == target) {
                return true;
            }
            else if (arrs[mid] < target) {
                left = mid + 1;
            }
            else {
                right = mid - 1;
            }
        }

        return false;
    }
}

